/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:
 * Date: 2024-09-19
 * Time: 16:02
 */
public class Solution {
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution1 {
        public int preIndex;
        public TreeNode buildTree(int[] preorder, int[] inorder) {

            return buildTreeChlid(preorder,inorder,0,inorder.length-1);
        }

        public TreeNode buildTreeChlid(int[] preorder,  int[] inorder, int inbegin, int inend) {
            //表明当前root没有子树了
            if(inbegin > inend){
                return null;
            }

            TreeNode root = new TreeNode(preorder[preIndex]);

            int rootIndex = findVal(inorder,inbegin,inend, preorder[preIndex]);
            preIndex++;
            root.left = buildTreeChlid(preorder,  inorder, inbegin,rootIndex-1);
            root.right = buildTreeChlid(preorder, inorder, rootIndex+1,inend);

            return root;
        }

        private int findVal(int[] order, int inbegin, int inend, int val){
            for(int i = inbegin;i <= inend; i++){
                if(order[i] == val){
                    return i;
                }
            }
            return -1;
        }
    }
}
